#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/09/12
# @Author   :Changshu
# @File     :practice_110.py

# 给定一个二叉树，判断它是否是高度平衡的二叉树。
import math

class TreeNode:
	def __init__(self,x):
		self.val=x
		self.left=None
		self.right=None


def isBalanced(root: TreeNode) -> bool:
	return height(root)>=0

def height(root):
	if root is None:
		return 0
	lh=height(root.left)
	rh=height(root.right)
	if lh>=0 and rh>=0 and abs(lh-rh)<=1:
		return max(lh,rh)+1
	return -1

if __name__ == '__main__':
	root = TreeNode(3)
	node1_1=TreeNode(9)
	node1_2=TreeNode(20)

	root.left=node1_1
	root.right=node1_2

	node2_1=TreeNode(15)
	node2_2 = TreeNode(7)
	node1_2.left=node2_1
	node1_2.right=node2_2

	b=isBalanced(root)
	print(b)